This invention relates to methods and apparatus for controlling output devices.
Most output devices can only output information in digitised form, and therefore cannot display continuous data precisely. For instance, video display units (VDUs) commonly display information using an array of pixels at discrete positions. When continuous data is to be displayed on such a device there is a need to convert the data to a digitised format. This is usually done by choosing digitised values that correspond closely to the continuous data.
One example is in the displaying of lines on a VDU. This commonly happens in graphics applications. FIG. 1 illustrates a grid of pixels 1,2, etc. and a pair of lines 3,4 which are to be displayed by illuminating certain ones of the pixels. The shaded pixels are illuminated to display the lines. Line 3 presents no problems because it lies neatly along a line of pixels, passing through the centre of each one. However, line 4 lies across the lines of pixels, and when this line is displayed there is a need to digitise the continuous nature of the line by choosing the pixels that best represent the line's absolute position. Some pixels (e.g. pixel 5) are easily chosen because the line 4 passes entirely through them. However, where the line passes partially through a pair of adjacent pixels (e.g. pixels 6 and 7) there is a need to decide which of those pixels should be illuminated.
A commonly used algorithm for digitising line segments, in this context is Bresenham's algorithm (see Jack Bresenham, 1965, “Algorithm for Computer Control of a Digital Plotter”, IBM Systems Journal 4(1), 25-30; reprinted in Interactive Computer Graphics, Qd. H Freeman, IEEE Computer Society, 1980). This algorithm involves stepping pixel-by-pixel along the major axis of the line (for line 4 in FIG. 1 this is in the direction marked by arrow 8) and keeping track of the fractional error between the current pixel (i.e. a digitised position) and the continuous position of the line. The fractional error is stored as a variable known as the discriminator, which is updated at each step of the algorithm along the major axis. The fractional error is kept within ±0.5 pixels by testing the discriminator at each step; if the error is too large then a jump of one pixel is also made along the minor axis of the line (arrow 9 in FIG. 1) and the fractional error reset accordingly. There are equivalent algorithms for similar applications such as plotting curved lines and texture mapping and shape filling (where the stepping is generally used to find the ends of lines used to fill a shape).
Modem graphics applications place a high demand on processing power and there is therefore a need to streamline the processing of graphics algorithms as much as possible. The same considerations apply to other fields where digitised data has to be output.